1. Field of the Invention
The present invention relates to link state routing protocols for establishment and maintenance of routes by routers in a network; more specifically, the present invention relates to distribution of dynamic routing metrics among routers of a network (e.g., a mobile ad hoc network or a mesh network) according to a link state routing protocol, optimized for minimal overhead while accommodating rapid topology changes in the network.
2. Description of the Related Art
Proposals have been made by Internet Engineering Task Force (IETF) groups for improved mobility support of Internet Protocol (IP) based mobile devices (e.g., laptops, IP phones, personal digital assistants, etc.) in an effort to provide continuous Internet Protocol (IP) based connectivity. The IETF has a Mobile Ad-hoc Networks (MANET) Working Group that is working to develop standardized MANET routing specification(s) for adoption by the IETF. According to the MANET Working Group, a “mobile ad hoc network” (MANET) is an autonomous system of mobile routers (and associated hosts) connected by wireless links—the union of which form an arbitrary graph. The routers are free to move randomly and organize themselves arbitrarily; thus, the network's wireless topology may change rapidly and unpredictably. Such a network may operate in a standalone fashion, or may be connected to the larger Internet.
The MANET system is particularly suited to low-power radio networks that may exhibit an unstable topology, where wireless propagation characteristics and signal quality between a wireless transmission source and a receiver can be difficult to model and quantify. In a MANET, the device address is tied to the device, not a topological location, as there is no fixed network infrastructure. When the addressed device moves, therefore, the motion changes the routing infrastructure. Hence, as described in an Internet Draft by Baker, entitled “An Outsider's View of MANET”(Mar. 17, 2002), the fundamental behavior of a MANET is that a routing node carries with it an address or address prefix, and when it moves, it moves the actual address; when this happens, routing must be recalculated in accordance with the new topology. For example, each mobile router retains its address prefix; hence, neighboring mobile routers in a MANET may have distinct address prefixes.
Existing MANET protocols focus on the internal connectivity within the unstable topology between mobile devices; however, the existing MANET protocols suffer from the disadvantage that they provide a poor model for connecting to a wide area network such as the Internet.
MANET protocols can be divided into the following types: stateful (proactive); and stateless (reactive). Proactive MANET protocols distribute routing information throughout the MANET network, enabling the routers within the MANET network to store route information before a data packet needs to be routed; hence, a router determines how to forward a packet based on accessing routing information from an internal table. However, proactive protocols suffer the disadvantage of requiring update messages to update obsolete route entries: the necessity for update messages increases with a corresponding desire for an improvement in route optimization.
Proactive MANET protocols can be subdivided into two subtypes, or “families”: Optimized Routing Approach (ORA), and Least Overhead Routing Approach (LORA). The ORA type protocols are similar to routing protocols used in the Internet, in that they stress maintaining the best states to maintain the shortest path routes, at the expense of requiring more control messages to exchange routes. An example of an ORA type routing protocol is Open Shortest Path First (OSPF) (as specified by the IETF Request for Comments (RFC) 2328), or Intermediate System-to-Intermediate System (IS-IS) protocol (specified by the International Organization for Standardization document ISO 10589). However, the OSPF and IS-IS protocols suffer from the disadvantage that they may require up to a minute to converge (i.e., complete protocol communications necessary to establish a connection) and hence may not be able to converge quickly enough for a mobile router that is moving from one location to another. For example, in the case of two vehicles passing each other, each having a mobile router, there may exist approximately ten seconds for the mobile routers to establish a connection; hence, routing protocols requiring up to a minute to converge would be unable to establish a connection. Also note that OSPF requires link-state advertisements (LSAs) to be refreshed as they expire after 3600 sec, resulting in substantial burdens in distributing the LSAs.
Reactive protocols were developed to address the slow convergence of ORA type proactive protocols, where routing information is acquired only when needed. Examples of reactive protocols are described in an Internet Draft by Perkins et al., “Ad hoc On-Demand Distance Vector (AODV) Routing (draft-ietf-manet-aodv.13), Feb. 17, 2003, and an Internet Draft by Johnson et al., “The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks (DSR)<draft-ietf-manet-dsr-09.txt>”, Apr. 15, 2003. Reactive protocols require less bandwidth than proactive protocols, but the latency for many applications will increase substantially, resulting in long delays. Such delays become quite apparent if a mobile user attempts to execute a bandwidth-intensive application on the ad hoc network instead of a typical high-speed wired connection on the Internet using a conventional connection (e.g., hard-wired LAN, cable modem, etc.).
The LORA family of proactive protocols attempts to provide a compromise between the fully stateful (ORA family) protocols and the fully stateless (reactive) protocols. One example of a LORA-type protocol is described in an Internet Draft by Garcia-Luna-Aceves, et al., “Source Tree Adaptive Routing (STAR) Protocol <draft-ietf-manet-star.00.txt>”, Oct. 22, 1999. However, even the disclosed STAR protocol suffers from disadvantages of requiring routing messages to establish a stable topology within the MANET network. For example, the STAR protocol requires a router to transmit the parameters of its source routing tree, including each link that the router needs to reach every known destination (and address range) in the ad hoc network or Internet. Although the STAR router attempts to conserve transmission bandwidth and energy by sending changes to its source routing tree only when the router detects new destinations, the possibility of looping, or the possibility of node failures or network partitions, the necessity of transmitting such parameters for each and every link still imposes substantial messaging requirements that affects bandwidth availability and network convergence times.
Efforts have been made to improve the performance of link state routing computations, also referred to Shortest Path First (SPF) based computations, based on using dynamic routing metrics instead of static metrics. In particular, OSPF has been based on a router using LSAs to flood the network with the assigned costs of the respective links utilized by the router, enabling other routers to calculate shortest routes to destinations. Use of dynamic routing metrics (e.g., early attempts at using dynamic routing metrics (e.g., in ARPANET) were unsuccessful because the dynamic routing metrics tended to introduce instabilities due to oscillation in the link delay values: routers receiving an advertisement of a dynamic routing metric (e.g., a low link delay value in a delay-based routing protocol) would immediately reconfigure their routes to use the advertised low delay link, creating substantially higher traffic on the advertised link; routers would then reroute their paths around the advertised link that had become a high delay link, causing the router to advertise the advertised link again as a low delay link. Such oscillation in the dynamic routing metrics caused routing instability.
Recent efforts to use dynamic routing metrics in link state routing protocols have attempted to reduce oscillation and instability by limiting the transmission of LSAs specifying the dynamic routing metrics: an LSA is output only if the dynamic routing metric specified in the LSA (e.g., link cost) changes by a multiple of a fixed value, also referred to as a “cost bucket”; hence, the router outputs an updated link cost value in an LSA only if the updated link cost value is deemed to have “moved” from one cost bucket to another; further, any link cost value that is near a boundary between two cost buckets must pass beyond a hysteresis range (e.g., 20%) before being moved to the new bucket. Although such attempts limit the number of shortest path first (SPF) computations that are performed by the routers and the associated instability, such attempts also adversely reduce the responsiveness of the network to changes in the dynamic routing metrics.